<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

    <script>
        /**
         * @param {number[][]} graph
         * @param {number[]} initial
         * @return {number}
         */
        var minMalwareSpread = function(graph, initial) {
            if (initial.length === 1) {
                return initial[0]
            }
            // 深度优先遍历，记录连通分量的长度
            let n = graph.length;
            // 创建一个数组用于存放各节点所对应的连通分量id值
            const ids = new Array(n).fill(0);
            // 创建一个哈希表用于存放各节点所对应的连通分量长度值
            const idsToSize = new Map();
            // 设置一个值用于表示同一个连通分量的id
            let id = 0;
            // 遍历邻接矩阵，并记录连通分量的长度和id
            for (let i = 0; i < n; i++) {
                // 若该行已经访问过，则跳过
                if (!ids[i]) {
                    //设置改节点对应连通分量的id
                    ids[i] = ++id
                        //size需随函数递归变化，故声明为数组
                    let size = [1]
                        // 则从graph[i][i]处开始查找该节点下的连通分量，以提高程序效率
                    findInfectNode(i, size, id, ids, graph)
                        // 执行完毕后向idsToSize哈希表存放id及其对应的连通分量长度
                    idsToSize.set(id, size[0])
                }
            }
            // 新建一个哈希表用于存放在该id下一共有多少个节点初始被感染
            const idsToInitial = new Map();
            initial.forEach((item) => {
                    // 如果哈希表中没有该id对应的个数，则新建后再进行+1操作
                    if (!idsToInitial.has(ids[item])) {
                        idsToInitial.set(ids[item], 0)
                    }
                    idsToInitial.set(ids[item], idsToInitial.get(ids[item]) + 1)
                })
                // 记录删除初始某节点能移除感染节点的最大值
            let maxRemove = 0
                // 记录满足条件节点的最小索引
            let answer = n
                // 遍历初始感染的每一项节点
            initial.forEach((item) => {
                    //如果在编号为ids[item]的连通分量下，初始感染的节点有且只有item一个，则删除他能够减少感染的节点为 idsToSize.get(ids[item])
                    // 若在编号为ids[item]的连通分量下，初始感染的节点大于1，则无论删不删除item都会导致所有节点感染，故减少感染的节点数为0
                    let remove = idsToInitial.get(ids[item]) === 1 ? idsToSize.get(ids[item]) : 0
                    if (remove > maxRemove) {
                        // 若移除item能够减少感染节点的个数大于maxremove
                        //则赋值给answer
                        maxRemove = remove
                        answer = item
                            // 当remove与maxRemove相等，且索引号较小时，修改满足条件索引
                    } else if (remove === maxRemove && item < answer) {
                        answer = item
                    }

                })
                // 遍历完后返回结果
            console.log('answer :>> ', answer);
            console.log('idsTosize :>> ', idsToSize);
            console.log('idsToInitial :>> ', idsToInitial);
            return answer
        };
        const findInfectNode = function(row, size, id, ids, graph) {
            for (let i = 0; i < graph.length; i++) {
                // 若不为对角线节点（不是自己连通自己）,且非访问过的节点，且该节点值为1，则在ids中将该节点设置为同一id(节点间互通),并将size自增1
                if (!ids[i] && row != i && graph[row][i] === 1) {
                    ids[i] = id
                    size[0] += 1
                        // 随后并立即交换行列(graph[i][j] == graph[j][i]),查找在j行是否有其他元素连通
                        // 使下一个递归中col=row+1避免陷入无穷递归
                    findInfectNode(i, size, id, ids, graph)
                }
            }
            return
        };


        // 测试案例1 预期输出 3
        // const a = [
        //     [1, 0, 0, 0],
        //     [0, 1, 0, 0],
        //     [0, 0, 1, 1],
        //     [0, 0, 1, 1]
        // ]
        // const b = [3, 1]
        // 测试案例2 预期输出 2
        // const a = [
        //     [1, 1, 0],
        //     [1, 1, 0],
        //     [0, 0, 1]
        // ]
        // const b = [0, 1, 2]
        // 测试案例3 预期输出 1
        // const a = [
        //     [1, 0, 1, 0],
        //     [0, 1, 0, 0],
        //     [1, 0, 1, 0],
        //     [0, 0, 0, 1]
        // ]
        // const b = [1]
        // 测试用例4 预期输出 2
        // const a = [
        //     [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        //     [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
        //     [0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
        //     [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        //     [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0],
        //     [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
        //     [0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
        //     [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
        //     [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
        //     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
        // ]
        // const b = [7, 8, 6, 2, 3]
        //测试用例5 预期输出0
        const a = [
            [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
            [0, 0, 1, 0, 1, 0, 0, 0, 0, 1],
            [0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
            [0, 0, 1, 0, 1, 0, 1, 0, 0, 1],
            [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
            [0, 0, 0, 0, 1, 1, 1, 0, 0, 1],
            [0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
            [0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
            [0, 1, 1, 1, 1, 0, 1, 0, 0, 1]
        ]
        const b = [9, 0, 2]
        minMalwareSpread(a, b)
    </script>
</body>

</html>